package 回溯;

import java.util.Arrays;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 火柴拼正方形473.java
 * @createTime 2023年01月13日 11:09:00
 */
public class 火柴拼正方形473 {
	public static void main(String[] args) {
		makesquare(new int[] {5,5,5,5,4,4,4,4,3,3,3,3});
	}

	public static boolean makesquare(int[] matchsticks) {
		if (matchsticks.length < 4) {
			return false;
		}
		int totalLength = Arrays.stream(matchsticks).sum();
		if (totalLength % 4 != 0) {
			return false;
		}
		Arrays.sort(matchsticks);
		return backTrace(matchsticks, new boolean[matchsticks.length], 0, totalLength / 4, 0);
	}

	public static boolean backTrace(int[] matchsticks, boolean[] used, int usedSize, int length, int sideNum) {
		if (sideNum == 4 && usedSize == matchsticks.length) {
			return true;
		}
		int tempLength = 0;
		for (int i = 0; i < matchsticks.length; i++) {
			//如果长度不为0，则需要进行处理
			if (used[i]) {
				continue;
			}
			if (tempLength + matchsticks[i] < length) {
				tempLength += matchsticks[i];
				used[i] = true;
				usedSize += 1;
				continue;
			} else if (tempLength + matchsticks[i] > length) {
				//如果当前结果>length 则说明这个长度不行，直接返回
				return false;
			} else {
				used[i]=true;
				return backTrace(matchsticks, used, usedSize+1, length, sideNum + 1);
			}
		}
		return false;
	}

}
